The present invention relates to methods and apparatuses for sorting timestamps in packet networks, and more particularly to a method and an apparatus for sorting timestamps in a system for scheduling packets in a packet network to guarantee data transfer rates to a data source and data transfer delays from a data source to a destination.
The implementation of Per-Virtual-Connection (Per-VC) schedulers which aim at approximating the Generalized Processor-Sharing (GPS) policy, as described in A. K. Parekh and R. G. Gallager, xe2x80x9cA Generalized Processor-Sharing Approach to Flow Control in Integrated Services Networks: The Single-Node Case,xe2x80x9d IEEE/ACM TRANSACTIONS ON NETWORKING, June 1993, pp. 344-357, which is incorporated herein by reference, is a central issue in next-generation switching systems for broadband packet networks, such as Asynchronous Transfer Mode (ATM) switches and Internet Protocol (IP) routers. In a market arena in which the cost targets are precipitously dropping, it is desirable to minimize the complexity involved in schedulers, and to make the cost differential with respect to systems with less sophisticated scheduling as small as possible.
The total implementation complexity of these GPS-related scheduling algorithms is a combination of the complexity of the function used as the system potential to compute the timestamps for the packets in the system, and the complexity involved in sorting the timestamps in order to select the packet with the minimum timestamp for transmission.
In recent years, several scheduling algorithms have been introduced, which algorithms use a system-potential function of minimal complexity. Examples are Self-Clocked Fair Queuing (SCFQ), as described in S. J. Golestani, xe2x80x9cA Self-Clocked Fair Queuing Scheme for Broadband Applications,xe2x80x9d PROCEEDINGS OF INFOCOM ""94, April 1994, pp. 636-646, which is incorporated herein by reference; Virtual Clock (VC), as described in L. Zhang, xe2x80x9cVirtual Clock: A New Traffic Control Algorithm for Packet Switching,xe2x80x9d ACM TRANSACTIONS ON COMPUTER SYSTEMS, May 1991, pp. 101-124, which is incorporated herein by reference; Frame-based Fair Queuing (FFQ), as described in D. Stiliadis and A. Varma, xe2x80x9cDesign and Analysis of Frame-based Fair Queuing: A New Traffic Scheduling Algorithm for Packet-Switched Networks,xe2x80x9d PROCEEDING OF SIGMETRICS ""96, May 1996, pp. 104-115, which is incorporated herein by reference; and Minimum-Delay Self-Clocked Fair Queuing (MD-SCFQ), as described in F. M. Chiussi and A. Francini, xe2x80x9cMinimum-Delay Self-Clocked Fair Queuing Algorithm for Packet-Switched Networks,xe2x80x9d PROCEEDINGS OF INFOCOM ""98, March 1998, which is incorporated herein by reference. In particular, among these algorithms, MD-SCFQ achieves both optimal delay properties and excellent fairness properties.
Given that scheduling algorithms achieving the desired performance with a system-potential function of minimal complexity are available, the major contribution to the total complexity comes from the sorting of timestamps to select which packet to serve, an operation that is common to all GPS-related schedulers and one that has to be performed every time a packet is transmitted or received.
The number of timestamps that have to be sorted is equal to the number of connections V supported by the scheduler. As an example, typical values of V in current ATM switches are in the tens of thousands of connections. The range of possible values that the timestamps can assume at any given time depends on the ratio between the maximum and minimum service rates that the scheduler is required to provide to the connections, and is typically very wide. Given the complexity of sorting a large number of timestamps over a wide range of possible values at the high speeds of interest in broadband packet networks, data structures that are specifically devised to be efficiently mapped into silicon must be used to make hardware implementation affordable. One popular technique to implement the sorting structure is the so-called calendar queue, which consists of an ordered collection of bins, one bin for each possible value of timestamp. The sorting of the timestamps occurs by physically separating the timestamps in the corresponding bins, and visiting the bins in order. The calendar queue uses a direct relation between position in memory and value of the timestamps to simplify the data structure required to perform the sorting. In the particular case of ATM networks, the granularity of interest to represent the timestamps is the timeslot, equal to the duration of transmission of a cell on a link. Accordingly, the calendar queue, to accurately implement the sorting in a GPS-related scheduler, should provide one bin per timeslot, and have as many bins as necessary to cover the possible range of values of the timestamps at any given time; again, with what is typical in current ATM switches, the required size of the calendar queue is very large and, consequently, the scheduler is still expensive. Similar considerations apply to data packet networks based on other technologies, such as IP networks.
To reduce the cost of the scheduler, approximations can be introduced to simplify the sorting task. Such approximations may negatively affect the delay properties of the initial scheduler. The challenge, of course, is to devise techniques that are simple to implement and introduce minimal degradation. A possible approach, as described in J. L. Rexford, A. G. Greenberg, and F. G. Bonomi, xe2x80x9cHardware-Efficient Fair Queuing Architectures for High-Speed Networks,xe2x80x9d PROCEEDINGS OF INFOCOM ""96, pp. 120-128, which is incorporated herein by reference, is to increase the granularity with which timestamps are represented and thus reduce the number of bins in the calendar queue accordingly. In a scheme such as SCFQ, which achieves delay bounds that are far from optimal, especially for connections with high service rate, the degradation introduced by the increased granularity is, after all, not that noticeable. In case of schemes such as FFQ and MD-SCFQ, which achieve optimal delay bounds and are therefore more desirable, such a technique would basically compromise those delay bounds, and in particular heavily penalize the high-rate connections.
The present invention relates to a method and an apparatus for sorting timestamps in a system for scheduling the transmission of data packets in a packet-switched network, which guarantees data transfer rates to data sources and data transfer delays from data sources to destinations and is cost-efficient to implement.
The present invention provides a technique to reduce the implementation cost of the sorting mechanism, which technique we have called the Logarithmic Calendar Queue (LCQ). The LCQ consists of a small ordered set of short calendar subqueues, in which the subqueues use bins of progressively increasing granularity. The name chosen for the technique comes from the fact that the set of subqueues can be viewed as a single calendar queue in which the granularity of the bins used to sort the timestamps increases logarithmically with the distance of the timestamps from the system potential at the time when they are computed. The LCQ increases the granularity in an optimal way, so that the relative degradation in delay bounds is very small and is the same for any connection, regardless of its service rate. Using the LCQ, the reduction in memory requirements, and consequently in cost, to implement the calendar queue is dramatic (e.g., three orders of magnitude in a typical scenario of a scheduler for a 622 Mbps link in a current ATM switch).